sunxin's Studio.

LinkedList (JDK8) 源码解析

源码
字数统计: 2.3k阅读时长: 11 min
2018/09/08 Share

LinkedList 源码解析

概述

LinkedList的底层数据结构是链表，所以它的优势是进行插入和删除操作效率很高,但是访问随机元素的效率比较低。它是线程不安全的，允许元素为null的双向链表，它可以被当作堆栈，队列或双端队列进行操作。

定义

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

  • 继承了 AbstractSequentialList<E>
  • 实现了List<E> 接口，可以进行队列操作
  • 实现了Deque<E> 接口，可以进行双端队列操作

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 集合元素的数量
transient int size = 0;

/**
 * Pointer to first node.  链表的头节点
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node. 链表的尾节点
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

/**
 * Constructs an empty list. 空构造，初始化的时候size为0，first和last的节点都是空
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 将集合中的所有元素都插入到链表中
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
   // 先调用this 执行无参构造
    this();
   // 把集合对象传递进去
    addAll(c);
}

Node

具有前驱和后继，可以看出是个双向链表

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
    E item; //元素值
    Node<E> next; //后继节点
    Node<E> prev;//前驱节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

增

addAll(Collection<? extends E> c)

增加一个元素肯定会修改 modCount

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * 
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<? extends E> c) {
    // 传递当前节点的Size，目前为0，然后把collection对象传递进去
    return addAll(size, c);
}


/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 * 以index为下标，插入集合c中的所有元素
 * @param index index at which to insert the first element
 *              from the specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);// 检查下标是否越界

    Object[] a = c.toArray();  // 把Collection转换成对象数组
    int numNew = a.length;// 集合的长度，也就是新增元素的数量
    if (numNew == 0) // 如果数量为0，则不增加，返回false
        return false;

    Node<E> pred, succ; //定义index节点的前驱节点和后置节点
    if (index == size) {// 表示在链表尾部增加
        succ = null;//后继节点为空
        pred = last;// 前驱节点变成队尾
    } else {
        succ = node(index);// 取出 index 位置的节点作为后置节点
        pred = succ.prev; // index 节点的前一个节点是前置节点
    }
   // 遍历数组，链表批量增加，通过遍历数组而依次插入。ArrayList是通过执行System.arrayCopy()进行批量复制插入
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null); // 使用前置节点pred，和元素e构建一个新的节点
        if (pred == null) // 如果前置节点为空
            first = newNode; // 新节点就是头节点
        else
            pred.next = newNode;// 否则前置节点的后节点是新节点
        pred = newNode; // 把当前的节点设置成前置节点，为下次添加做准备
    }

    if (succ == null) { // 循环结束之后，判断后置节点如果是空，说明此时是在队尾添加
        last = pred;// 设置成尾节点
    } else { // 否则就是在队中插入
        pred.next = succ; // 更新前置节点的后置节点
        succ.prev = pred; // 更新后置节点的前置节点
    }

    size += numNew; // 修改数量size
    modCount++; // 更新修改次数
    return true;
}


/**
 * Returns the (non-null) Node at the specified element index.
 * 通过index 获取一个节点，会进行折半查找，提高效率
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

add(E e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Appends the specified element to the end of this list.
 * 在尾部插入单个节点元素
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last; // 记录原来尾部节点
    final Node<E> newNode = new Node<>(l, e, null); // 通过尾部节点和元素e构造一个新节点
    last = newNode; // 更新尾部节点
    if (l == null) // 如果尾部节点为空，说明链表是空，需要一个头结点
        first = newNode;
    else //否则更新原来的尾部节点的后置节点为现在的尾节点
        l.next = newNode;
    size++; // 数量
    modCount++; //修改次数
}

add(int index, E element)

插入单个元素到指定位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    checkPositionIndex(index); //下标检查

    if (index == size) // 在尾节点插入
        linkLast(element); 
    else
        linkBefore(element, node(index)); //在中间插入
}

/**
 * Inserts element e before non-null Node succ. 折半查找
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

删

E remove(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Removes the element at the specified position in this list.  Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * Returns the element that was removed from the list.
 *
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    checkElementIndex(index);// 检查下标越界
    return unlink(node(index));// 从链表上删除某个节点
}

/**
 * Unlinks non-null node x.
 */
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;// 拿到这个元素
    final Node<E> next = x.next; // 拿到后置节点
    final Node<E> prev = x.prev; // 拿到前驱节点

    if (prev == null) { // 前置节点为空，那么这个节点就是头结点
        first = next;
    } else {
        prev.next = next; // 让当前节点前置节点直接指向当前节点的后置节点
        x.prev = null; // 前置节点置为空
    }

    if (next == null) { // 如果后置节点为空，说明是尾节点
        last = prev; // 直接让他的前置节点作为尾节点就行
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element; // 返回取出的元素值
}

boolean remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * 删除指定的元素
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
public boolean remove(Object o) {
    if (o == null) { // 分情况遍历
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

改

E set(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    checkElementIndex(index); //检查下标
    Node<E> x = node(index); // 利用折半查找找到index对应的节点
    E oldVal = x.item; // 拿到这个节点对应的元素
    x.item = element; //修改元素值
    return oldVal;
}

查

E get(int index)

1
2
3
4
5
6
7
8
9
10
11
/**
 * Returns the element at the specified position in this list.
 * 根绝下标查询
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);// 判断是否越界
    return node(index).item;
}

int indexOf(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the lowest index {@code i} such that
 * 根据节点对象查找节点的下标
 * @param o element to search for
 * @return the index of the first occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
public int indexOf(Object o) {
    int index = 0;
    if (o == null) { // 如果目标对象为null，链表允许存入null值
        for (Node<E> x = first; x != null; x = x.next) {  // 遍历链表
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

Object[] toArray()

1
2
3
4
5
6
7
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

– Over –

原文作者：Sun xin

原文链接：http://sunxin.tech/2018/09/08/LinkedList (JDK8) 源码解析/

发表日期：September 8th 2018, 9:22:44 am

更新日期：April 9th 2018, 8:59:47 pm

CATALOG
  1. 1. LinkedList 源码解析
    1. 1.1. 概述
    2. 1.2. 构造函数
    3. 1.3. Node
    4. 1.4. 增
      1. 1.4.1. addAll(Collection<? extends E> c)
      2. 1.4.2. add(E e)
      3. 1.4.3. add(int index, E element)
    5. 1.5. 删
      1. 1.5.1. E remove(int index)
      2. 1.5.2. boolean remove(Object o)
    6. 1.6. 改
      1. 1.6.1. E set(int index, E element)
    7. 1.7. 查
      1. 1.7.1. E get(int index)
      2. 1.7.2. int indexOf(Object o)
    8. 1.8. Object[] toArray()
Total : 32
2020
2019
2018
开发艺术探索 源码分析 开发艺术探索 源码 源码 设计模式 Git 面试 JavaScript 协程 Kotlin in Action Android设计模式 实用 个人博客 UML 记录 感悟 踩坑实践 随想 自定义View
Android开发艺术探索 一步一步进入高级行列 Java Android-三方开源库 设计模式系列 Git 计算机网络 JavaScript Kotlin Android技术 UML 踩坑实践 Life 源码分析 源码 Android技术/个人博客 自定义View系列